package com.gxc.string;

/**
 * 找出字符串中第一个匹配项的下标

 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。
 * 如果 needle 不是 haystack 的一部分，则返回  -1
 */
public class StrStr {

    public int strStr(String haystack, String needle) {
        int m = haystack.length(), n = needle.length();
        int[] next = generateNext(needle);

        int i = 0, j = 0;
        while (i < m && j < n) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else if (next[j] > -1){
                j = next[j];
            } else {
                i++;
            }
        }
        return j == n?i-j:-1;
    }

    public int[] generateNext(String needle) {
        int n = needle.length();
        int[] next = new int[n+1];
        next[0] = -1;
        next[1] = 0;

        char[] charArray = needle.toCharArray();
        int cm = 0;
        int i = 2;
        while (i < needle.length()) {
            if (charArray[i-1] == charArray[cm]) {
                next[i] = cm+1;
                cm++;
                i++;
            } else if (next[cm] > -1) {
                cm = next[cm];
            } else {
                i++;
            }
        }
        return next;
    }

}
